package com.wwlwxg.algorithm.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式转后缀表达式
 * 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
 * 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -
 * 1. 从左至右扫描，将3和4压入堆栈；
 * 2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
 * 3. 将5入栈；
 * 4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
 * 5. 将6入栈；
 * 6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
 * 四、中缀转后缀表达式
 *
 * 1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
 * 2. 从左至右扫描中缀表达式；
 * 3. 遇到操作数时，将其压s2；
 * 4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
 *  1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
 *  2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
 *  3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
 */
public class InFixToSuffix {

	public static void main(String[] args) {
		String expression = "63 * ( ( 3 + 6 ) * ( ( 1 + 2 ) + ( 3 + 2 ) ) )";
		char c1 = '/';
		char c2 = '+';
		char c3 = '-';
		char c4 = '*';
		char c5 = '(';
		char c6 = ')';
		List<String> list = getList(expression);
		String calculate = calculate(list);
		System.out.println(calculate);
	}

	/**
	 * 把所有元素放到一个集合
	 * / 47
	 * + 43
	 * - 45
	 * * 42
	 * ( 40
	 * ) 41
	 * 0 48
	 * 9 57
	 * @param expression
	 * @return
	 */
	private static List<String> getList(String expression) {
		List<String> dataList = new ArrayList<>();
		char[] chars = expression.toCharArray();
		int tmp = 0;
		int state = 0;
		for(char c : chars) {
			if(c == ' ') {
				continue;
			}
			if(c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
				if(state == 0) {
					dataList.add(tmp+"");
				}
				dataList.add(c+"");
				tmp = 0;
				state = -1;
				continue;
			}
			tmp = tmp * 10 + (c - 48);
			state = 0;

		}

//		System.out.println(dataList);
//		String[] split = expression.split(" ");
//		List<String> list = new ArrayList<>();
//		for(String c : split) {
//			list.add(c+"");
//		}

		return dataList;
	}

	/**
	 * 转换方法
	 * @param list
	 * @return
	 */
	private static String calculate(List<String> list) {
		// 存放符号
		Stack<String> s1 = new Stack<>();
		// 存储中间结果
		Stack<String> s2 = new Stack<>();
		for(String str : list) {
			if(str.matches("\\d+")) {
				s2.push(str);
			} else {
				if(s1.empty()) {
					// 如果为空，则直接入栈
					s1.push(str);
				} else if(str.equals("(")) {
					// 如果为 "(" 直接入栈
					s1.push(str);
				} else if(s1.peek().equals("(")) {
					// 如果栈顶为 "(" 直接入栈
					s1.push(str);
				} else if(priority(str) > priority((String)s1.peek())) {
					// 如果优先级大于栈顶优先级
					s1.push(str);
				} else if(str.equals(")")) {
					// 循环将括号在s1取出压入s2
					while (true) {
						String pop = (String)s1.pop();
						if(pop.equals("(")) {
							break;
						} else {
							s2.push(pop);
						}
					}
				} else {
					// 如果都不满足就取出 s1 符号push到 s2,直到满足条件再将符号push到s1
					while (true) {
						if(s1.empty() || s1.peek().equals("(") || priority(str) > priority(s1.peek())) {
							s1.push(str);
							break;
						} else {
							String pop = s1.pop();
							s2.push(pop);
						}
					}
				}
			}
		}

		if(!s1.empty()) {
			while (true) {
				String pop = s1.pop();
				s2.push(pop);
				if(s1.empty()) {
					break;
				}
			}
		}

		if(!s2.empty()) {
			while (true) {
				String pop = s2.pop();
				s1.push(pop);
				if(s2.empty()) {
					break;
				}
			}
		}

		String value = "";
		// 取出 s1 元拼接，就是后缀表达式
		while (true) {
			value += s1.pop() + " ";
			if(s1.empty()) {
				break;
			}
		}
		return value;
	}

	/**
	 * 判断优先级
	 * @param str
	 * @return
	 */
	private static int priority(String str) {
		if(str.equals("*") || str.equals("/")) {
			return 1;
		} else if(str.equals("+") || str.equals("-")) {
			return 0;
		} else {
			return -1;
		}
	}


}
